package com.javabasic.algorithm.leetcode;

import java.util.Arrays;
import java.util.Random;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [710. 黑名单中的随机数 - 力扣（LeetCode）](https://leetcode.cn/problems/random-pick-with-blacklist/)
 * @since Created by work on 2022/6/26 09:58
 */
public class RandomPickWithBlacklist {

}

class Solution710 {
    private static Random random = new Random();
    private int randomLen;
    private int[] blacklist;
    private int length;

    public Solution710(int n, int[] blacklist) {
        length = blacklist.length;
        randomLen = n - length;
        Arrays.sort(blacklist);
        this.blacklist = blacklist;
    }

    public int pick() {
        int index = random.nextInt(randomLen);
        return adjustIndex(index);
    }

    /**
     * 动态模拟
     * @param index
     * @return
     */
    private int adjustIndex(int index) {
        int lessIndexNum = 0;
        int tagIndex = 0;
        for (int i = 0; i < length; i++) {
            if (blacklist[i] <= index) {
                lessIndexNum++;
                tagIndex = i;
            } else {
                break;
            }
        }

        tagIndex++;
        while (lessIndexNum != 0) {
            index++;
            if (tagIndex < length && index == blacklist[tagIndex]) {
                tagIndex++;
            } else {
                lessIndexNum--;
            }
        }

        return index;
    }
}

